题解 loj2349「JOI 2018 Final」团子制作

发表于 | 更新于

$Description$

你是一个制作团子的师傅，现在，你正想用竹签把团子串成一串。

团子被放置在长为$N$行，宽为$M$列的隔开的格子里，每个格子里都放着一个团子。每个团子的颜色是红、绿与白中的一种。

你可以选择三个从左到右，或者从上到下的连续的格子，把格子中的团子串成一串，按照这个顺序，一串团子串上正好会有三个团子。

现在，你希望尽可能多做些颜色按照红绿白顺序的团子串，并且团子在串上的顺序必须与从格子中取出的顺序相同。需要注意的是，同一个团子只能被串在一串团子串上。

你最多能制作多少串团子串呢？

给出放置在每个格子上的团子的颜色，你需要计算最多能制作的团子串的数量。团子串的颜色必须按照红、绿、白的顺序。

$Solution$

很有意思的$DP,$考虑团子串中间的$G$不在同一对角线的团子串不会互相影响，所以在对角线上进行$DP.$对于一条对角线，我们从左下向右上$DP,f_{i,0/1}$表示当前对角线从左下到右上第$i$个团子可以与左右或上下的团子构成团子串$,0/1$表示跟左右/上下构成团子串。

$f_{i,j}$只能由$f_{k,t}(0\leqslant k< i,t=0/1)$或$f_{i-1,j}$转移过来。

转移很好想，但是难想在考虑到不在同一对角线的团子串不会互相影响。

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define re register
#define N 3012
using namespace std;

inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
char s[N][N];
int n,m,f[N][2],ans;
int calc(int x,int y){
    return (s[x-1][y]=='R'&&s[x][y]=='G'&&s[x+1][y]=='W')<<1|(s[x][y-1]=='R'&&s[x][y]=='G'&&s[x][y+1]=='W');
}
signed main(){
    n=read(),m=read();
    for (int i=1;i<=n;++i)scanf("%s",s[i]+1);
    for (int i=1,j=1;i<=n+m-1;++i,j=1){
        int mx=0;
        for (int x=min(i,n),y=max(1,i-n+1);x&&y<=m;--x,++y){
            int opt=calc(x,y);++j;f[j][0]=f[j][1]=0;
            mx=max(mx,max(f[j-2][0],f[j-2][1]));
            if (opt&1)f[j][0]=max(f[j-1][0],mx)+1;
            if (opt&2)f[j][1]=max(f[j-1][1],mx)+1;
        }
        ans+=max(mx,max(max(f[j-1][0],f[j][0]),max(f[j-1][1],f[j][1])));
    }
    printf("%d\n",ans);
    return 0;
}